﻿/*
题目：正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

https://leetcode.cn/problems/regular-expression-matching/description/
*/

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <array>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <algorithm>
#include <sstream>
#include <functional>
#include <random>

using namespace std;

class Solution {
public:
    bool isMatch(string s, string p) {
        int slen = s.size(), plen = p.size();

        // dp[i][j] 表示 s[i - 1] 和 p[j - 1] 是否匹配
        vector<vector<bool>> dp(slen + 1, vector<bool>(plen + 1, false));

        dp[0][0] = true;
        for (int i = 0; i < plen; i += 2) {
            if (i + 1 < plen && (::isalpha(p[i]) || p[i] == '.' || p[i] == '*') && p[i + 1] == '*') {
                dp[0][i + 2] = true;
            }
            else break;
        }

        for (int i = 1; i <= slen; i++) {
            for (int j = 1; j <= plen; j++) {
                // 第一种情况, 都是字母; 第二种情况，存在 *
                if (s[i - 1] == p[j - 1] || p[j - 1] == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                // 第三种情况，* 可以和前面的元素组合，表示 0 个或者无数个
                else if (p[j - 1] == '*') {
                    // 1. 可以直接舍弃当前组合，也就是 0 个
                    dp[i][j] = dp[i][j - 2];

                    // 如果相等
                    if (s[i - 1] == p[j - 2] || p[j - 2] == '.') {
                        // dp[i][j - 1] 表示匹配一次
                        // dp[i - 1][j] 表示匹配无数次，可以当前 s[i] 这个元素不存在
                        dp[i][j] = dp[i][j] | dp[i][j - 1] | dp[i - 1][j];
                    }
                }
            }
        }

        return dp[slen][plen];
    }
};
